﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
using System.IO;
using GraphJohnsonPrj;

namespace DirectedGraphCycle
{
    abstract class FindAllCycle
    {
        public abstract class Cycle
        {
            public enum Direction
            {
                LEFT, RIGHT
            }

            public int Begin { get; protected set; }
            public List<int> Vertexes { get; protected set; }

            public Cycle(List<int> vertexes)
            {
                Vertexes = vertexes.ToList(); // deep copy
                Normalize();
            }

            private void Normalize()
            {
                int indexMin = 0;
                for (int i = 0; i < Vertexes.Count; ++i)
                {
                    if (Vertexes[i] < Vertexes[indexMin])
                    {
                        indexMin = i;
                    }
                }
                Begin = Vertexes[indexMin];

                Direction d = ChooseDirection(indexMin);
                if (indexMin == 0)
                {
                    if (d == Direction.RIGHT)
                    {
                        Vertexes.RemoveAt(0);
                    }
                    else // LEFT
                    {
                        Vertexes.Reverse();
                        Vertexes.Remove(Vertexes.Count - 1);
                    }
                    return;
                }

                List<int> newVertexes = new List<int>(Vertexes.Count);
                int index = indexMin;
                if (d == Direction.RIGHT)
                {
                    for (int i = 1; i < Vertexes.Count; ++i)
                    {
                        ++index;
                        if (index >= Vertexes.Count) index = 0;
                        newVertexes.Add(Vertexes[index]);
                    }
                }
                else // LEFT
                {
                    for (int i = 1; i < Vertexes.Count; ++i)
                    {
                        --index;
                        if (index < 0) index = Vertexes.Count;
                        newVertexes.Add(Vertexes[index]);
                    }
                }
                Vertexes = newVertexes;
            }

            protected abstract Direction ChooseDirection(int indexMin);

            public override string ToString()
            {
                return ToString("-");
            }

            public string ToString(string seperator)
            {
                StringBuilder strBuilder = new StringBuilder(Vertexes.Count + (Vertexes.Count - 1) * seperator.Length);
                strBuilder.Append(Begin).Append(seperator);
                foreach (int vertex in Vertexes)
                    strBuilder.Append(vertex).Append(seperator);
                strBuilder.Append(Begin);
                return strBuilder.ToString();
            }
        }

        public class CycleComparer : EqualityComparer<Cycle>, IComparer<Cycle>
        {
            public int DoCompare(Cycle x, Cycle y)
            {
                if (x == null && y == null) return 0;
                if (x == null) return -1;
                if (y == null) return 1;
                //
                if (x.Begin != y.Begin) return x.Begin - y.Begin;
                //
                IEnumerator<int> xer = x.Vertexes.GetEnumerator();
                IEnumerator<int> yer = y.Vertexes.GetEnumerator();
                while (true)
                {
                    bool xHasNext = xer.MoveNext();
                    bool yHasNext = yer.MoveNext();
                    if (!xHasNext && !yHasNext) return 0;
                    if (!xHasNext) return -1;
                    if (!yHasNext) return 1;
                    //
                    if (xer.Current != yer.Current) return xer.Current - yer.Current;
                }
            }

            public override bool Equals(Cycle x, Cycle y)
            {
                return DoCompare(x, y) == 0;
            }

            public override int GetHashCode(Cycle obj)
            {
                int hashCode = obj.Begin + obj.Vertexes.Sum();
                return hashCode;
            }

            int IComparer<Cycle>.Compare(Cycle x, Cycle y)
            {
                return DoCompare(x, y);
            }
        }

        public MainForm GUI = null;
        public string filePathInput = string.Empty;
        public string filePathOutput = string.Empty;
        protected bool hasCycle = false;
        protected int numOfCycle = 0;
        protected int displayLength = 0;

        protected const int MAX_WRITE_ATIME = 10000;
        protected const int THRESHOLD_LENGTH_DISPLAY_UI = 100000;
        protected static readonly string HOLDER_FOR_NUM_OF_CYCLE = new string(' ', 20);
        protected static CycleComparer CycleCmper = new CycleComparer();
        protected List<Cycle> cycles = null;
        protected List<int>[] adjacencyListOriginal = null;
        protected bool[] blocked = null;
        protected List<int>[] B = null;
        protected List<int> stack = null;
        protected int numNodes = 0;

        public void readGraphData()
        {
            try
            {
                using (System.IO.StreamReader file = new System.IO.StreamReader(filePathInput))
                {
                    // read the number of vertexes
                    int numVertex;
                    readTheNumberOfVertexes(file, out numVertex);

                    // read each line
                    adjacencyListOriginal = new List<int>[numVertex];
                    string line = null;
                    this.numNodes = 0;
                    int icurVertex = 0, w = 0;
                    for (; icurVertex < numVertex && (line = file.ReadLine()) != null; ++icurVertex)
                    {
                        if (string.IsNullOrWhiteSpace(line))
                        {
                            adjacencyListOriginal[icurVertex] = new List<int>(0);
                            continue;
                        }
                        string[] adjVertexes = line.Split(' ');
                        adjacencyListOriginal[icurVertex] = new List<int>(adjVertexes.Length);
                        for (int j = 0; j < adjVertexes.Length; ++j)
                        {
                            adjVertexes[j] = adjVertexes[j].Trim();
                            if (int.TryParse(adjVertexes[j], out w))
                                addToAdjMatrix(icurVertex, w);
                        }
                        this.numNodes += adjacencyListOriginal[icurVertex].Count;
                    }
                    while (icurVertex < numVertex)
                    {
                        adjacencyListOriginal[icurVertex] = new List<int>(0);
                        ++icurVertex;
                    }
                }
            }
            catch (Exception ex)
            {
                if (!Program.ConsoleMode)
                    MessageBox.Show(ex.Message, "Error in buildGraph()", MessageBoxButtons.OK, MessageBoxIcon.Error);
                else
                    Environment.Exit(-1);
            }
        }

        private void readTheNumberOfVertexes(System.IO.StreamReader file, out int numVertex)
        {
            string line = null;
            numVertex = -1;
            do
            {
                line = file.ReadLine();
                if (line == null)   // reach end of file
                {
                    throw new System.IO.IOException("Empty file");
                }
            }
            while (string.IsNullOrWhiteSpace(line));
            //
            numVertex = int.Parse(line);
            if (numVertex <= 0)
                throw new System.IO.InvalidDataException(string.Format("nvertex ({0}) <= 0", numVertex));
        }

        protected abstract void addToAdjMatrix(int v1, int v2);

        public abstract List<Cycle> getAllCycles();

        protected abstract Cycle NewCycle(List<int> vertexes);

        public void printFinalCyclesToFile()
        {
            string strNumOfCycle = numOfCycle.ToString("#,##0");
            using (FileStream fs = File.Open(filePathOutput, FileMode.OpenOrCreate, FileAccess.Write))
            {
                foreach (char c in strNumOfCycle)
                    fs.WriteByte((byte)c);
            }
            if (GUI != null)
                GUI.printNumOfCycleToGUI(numOfCycle);
        }

        protected void PrintAPart()
        {
            cycles.Sort(CycleCmper);
            if (!hasCycle)
            {
                hasCycle = true;
                printFirstCyclesToFile();
            }
            else
            {
                printAppendCyclesToFile();
            }
            numOfCycle += this.cycles.Count;
            this.cycles.Clear();
        }

        protected void printFirstCyclesToFile()
        {
            using (StreamWriter sw = new StreamWriter(filePathOutput))
            {
                sw.WriteLine(HOLDER_FOR_NUM_OF_CYCLE);
                if (cycles == null || cycles.Count <= 0)
                {
                    //sw.WriteLine(0);
                    return;
                }
                else
                {
                    //sw.WriteLine(cycles.Count);
                    int maxCapcity = cycles.Count * adjacencyListOriginal.Length / 2;
                    if (maxCapcity > THRESHOLD_LENGTH_DISPLAY_UI) maxCapcity = THRESHOLD_LENGTH_DISPLAY_UI;
                    StringBuilder line = new StringBuilder(maxCapcity);
                    foreach (Cycle cycle in cycles)
                    {
                        sw.WriteLine(cycle);
                        if (GUI != null && line.Length < THRESHOLD_LENGTH_DISPLAY_UI)
                        {
                            line.AppendLine(cycle.ToString());
                            if (line.Length >= THRESHOLD_LENGTH_DISPLAY_UI)
                                line.Append("...");
                        }
                    }
                    if (GUI != null)
                    {
                        displayLength = line.Length;
                        GUI.printFirstCyclesToGUI(line.ToString());
                    }
                }
            }
        }

        protected void printAppendCyclesToFile()
        {
            using (StreamWriter sw = new StreamWriter(filePathOutput, true))
            {
                if (cycles == null || cycles.Count <= 0)
                {
                    return;
                }
                else
                {
                    //sw.WriteLine(cycles.Count);
                    int maxCapcity = cycles.Count * adjacencyListOriginal.Length / 2;
                    if (maxCapcity > THRESHOLD_LENGTH_DISPLAY_UI) maxCapcity = THRESHOLD_LENGTH_DISPLAY_UI;
                    if (GUI != null && displayLength >= THRESHOLD_LENGTH_DISPLAY_UI) maxCapcity = 0;
                    StringBuilder line = new StringBuilder(maxCapcity);
                    foreach (Cycle cycle in cycles)
                    {
                        sw.WriteLine(cycle);
                        if (GUI != null && displayLength + line.Length < THRESHOLD_LENGTH_DISPLAY_UI)
                        {
                            line.AppendLine(cycle.ToString());
                            if (displayLength + line.Length >= THRESHOLD_LENGTH_DISPLAY_UI)
                                line.Append("...");
                        }
                    }
                    if (GUI != null && line.Length > 0)
                    {
                        displayLength += line.Length;
                        GUI.printAppendCyclesToGUI(line.ToString());
                    }
                }
            }
        }
    }
}
